1. Field of the Invention
The present invention generally relates to variable length decoding. More particularly, the present invention relates to bit-stream extraction in audio, imaging and video decompression applications.
2. Description of Related Art
Most existing techniques either offer a single-format variable length decoding engine or include a simple programmable engine that does most of the computations in software. The efficiency of the programmable engine is also limited because it typically provides acceleration only for the bit stream extraction portions of the problem.
Bit-field extraction is a critical part of several of image, video and audio decompression algorithms which use Huffman coding techniques to encode variables in the bitstreams. In Huffman coding based schemes, code words which occur very frequently are represented using shorter length bit fields while infrequent code words are represented using longer length bit fields. When the average bit rate is high (greater than 1 Mbits/sec), the number of times such variable length decoding (VLD) is done each second becomes very high. For example, for a bitstream at 8 Mbits/sec, assuming an average number of bits per field is 4, we need to decode 2 Mfields/sec. That is, for every cycle spent to decode such fields in software an extra 2 MIPS is required. For example, in a conventional MPEG-4 video decoder implemented on ARM7TDMI, approximately 50 cycles/field is required for VLD and Inverse Quantization. Consequently, decoding at 8 Mbits/sec would consume 100 MIPS which significantly exceeds the capabilities of current ARM7TDMI processor.
Conventional software engines of the use specific instructions to accelerate bit processing. For example, ARM processors have a count leading zero (CLZ) instruction for bit handling1. In another example, programmable DSP processors such as the Texas Instruments TI C64x have instructions such as Bit Field Extract, Set and Clear to handle bit processing2. Processors such as Equator's BSP16 have a dedicated 16-bit RISC engine to offload bit processing functions from the main CPU. This bit engine is fully software programmable in C. Methods conventionally used in bitstream decoding are taught by W. Lee, and C. Basoglu, “MPEG-2 Decoder Implementation on MAP-CA Media Processor Using the C Language,” Proc. SPIE: Media Processors 2000, vol. 3970, Int'l Soc. for Optical Eng., Bellingham, Wash., 2000, pp. 27-36. While these approaches may provide some benefit by accelerating bit processing functions, the same inherent restrictions remain. In particular, such engines are not very good at processing bit streams that include varieties of HuffmanNariable length decoding. In addition, these engines are wasteful of processing power on simple calculations and lookups. 1 See, e.g., http://www.arm.com/products/CPUs/ARM926EJ-S.html2 See, e.g., http://focus.ti.com/docs/prod/folders/print/tms320c6411.html
Philips's Trimedia processors added a bit-streamNLD engine that accelerated MPEG-1/MPEG-2 video standards. However, this product had limited functionality and cannot be used to handle most encoding schemes. There are several examples in the industry that have taken this approach. Hence, there are no known bit stream engines that can handle variety of audio and video formats and provide a flexibility of programmability.
Parallel multiple-symbol VLD systems have been implemented3. However, such systems implement VLD processing in a standard specific way and can address only 1 or 2 where substantial similarity exists between standards. The resulting systems are inflexible and cannot handle other existing or newly defined standards.